import "babel-polyfill";
import Integer from "../number/integer";

const {min} = Math;
const {zero, one, abs, negate, eq, compare, add, subtract, multiply, divmod, mod, exactDivide, shl} = Integer;

export var gcd = function() {
    var result = zero;
    for (let number of arguments) {
        let [s1, m] = result.extractEven();
        let [s2, n] = abs(number).extractEven();
        if (Integer.compare(m, n) < 0) {
            [m, n] = [n, m];
        }
        while (n.sign) {
            if (n.bitLength < 16 || m.bitLength - n.bitLength >= 20) {
                [m, n] = [n, mod(m, n).extractEven()[1]];
            } else {
                m = subtract(m, n).extractEven()[1];
                if (compare(m, n) < 0) {
                    [m, n] = [n, m];
                }
            }
        }
        result = shl(m, min(s1, s2));
        if (eq(result, one)) {
            return one;
        }
    }
    return result;
};

export var exGCD = function(m, n) {
    m = Integer.from(m);
    n = Integer.from(n);
    var sign = {m: m.sign, n: n.sign};
    m = abs(m);
    n = abs(n);
    var [a1, a2, b1, b2] = [zero, one, one, zero];
    while (m.sign) {
        let q;
        [[q, m], n] = [divmod(n, m), m];
        [a1, a2] = [a2, subtract(a1, multiply(q, a2))];
        [b1, b2] = [b2, subtract(b1, multiply(q, b2))];
    }
    if (sign.m < 0) {
        a1 = negate(a1);
    }
    if (sign.n < 0) {
        b1 = negate(b1);
    }
    return [n, a1, b1];
};

export var invmod = function(m, n) {
    var x = exGCD(m, n)[1];
    return x.sign >= 0 ? x : add(n, x);
};

export var lcm = function() {
    var result = one;
    for (let number of arguments) {
        number = Integer.abs(number);
        if (number.sign === 0) {
            return zero;
        }
        result = multiply(result, exactDivide(number, gcd(result, number)));
    }
    return result;
};

export var chineseRemainder = function() {
    var M = one;
    var y = zero;
    for (let [remainder, m] of arguments) {
        y = add(y, multiply(M, mod(multiply(subtract(remainder, y), invmod(M, m)), m)));
        M = multiply(M, m);
    }
    return y;
};
